package data_structure;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class leetcode_0101 {
    public boolean isSymmetric(TreeNode root) {
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>();
        List<TreeNode> stack=new LinkedList<>();
        stack.add(root);
        int count=1;
        int current=0;
        int current0=0;
        while(count!=current0){
            current0=0;
            for(int i=0;i<count;++i){
                TreeNode node=stack.remove(0);
                if(node==null){
                    list1.add(-101);
                    stack.add(null);
                    stack.add(null);
                    current0+=2;
                    current+=2;
                }
                else{
                    list1.add(node.val);
                    stack.add(node.left);
                    stack.add(node.right);
                    if(node.left==null){
                        current0+=1;
                    }
                    if(node.right==null){
                        current0+=1;
                    }
                    current+=2;
                }

            }
            count=current;
            current=0;
        }
        stack.clear();
        stack.add(root);
        count=1;current=0;current0=0;
        while(count!=current0){
            current0=0;
            for(int i=0;i<count;++i){
                TreeNode node=stack.remove(0);
                if(node==null){
                    list2.add(-101);
                    stack.add(null);
                    stack.add(null);
                    current0+=2;
                    current+=2;
                }
                else{
                    list2.add(node.val);
                    stack.add(node.right);
                    stack.add(node.left);
                    if(node.left==null){
                        current0+=1;
                    }
                    if(node.right==null){
                        current0+=1;
                    }
                    current+=2;
                }

            }
            count=current;
            current=0;
        }
        int len=list1.size();
        for(int i=0;i<len;++i){
            if(list1.get(i)!=list2.get(i)) return false;
        }
        return true;
    }
}
